#include <set>
#include <stdexcept>
#include <ctime>
#include <iostream>
#include "IGraph.h"

using namespace std;

const int MAX_VERTICES_NUMBER = 100;
const int MAX_EDGES_NUMBER = 140;
const int MAX_TEST_NO = 10;
//dynamic_cast<child*>(basePtr);

inline vector<Edge> createRandomGraph(int verticesNumber) {
	set<Edge> edgesSet;
	int edgesNumber = rand() % MAX_EDGES_NUMBER;

	for (int i = 0; i < edgesNumber; ++i) {
		int vertexFrom = rand() % verticesNumber;
		int vertexTo = rand() % verticesNumber;
		edgesSet.insert(Edge(vertexFrom, vertexTo));
	}
	vector<Edge> edgesList(edgesSet.begin(), edgesSet.end());
	return edgesList;
}

inline vector<Edge> createFullGraph(int verticesNumber) {
	vector<Edge> result;
	for (int vertexFrom = 0; vertexFrom < verticesNumber; ++vertexFrom) {
		for (int vertexTo = 0; vertexTo < verticesNumber; ++vertexTo) {
			result.push_back(Edge(vertexFrom, vertexTo));
		}
	}
	return result;
}

inline vector<Edge> createAcyclicGraph(int verticesNumber) {
	vector<Edge> result;
	double probability = 0.1;
	for (int vertexFrom = 0; vertexFrom < verticesNumber; ++vertexFrom) {
		for (int vertexTo = vertexFrom + 1; vertexTo < verticesNumber; ++vertexTo) {
			double randomDouble = (rand() % 1000) / 1000;
			if (probability > randomDouble)
				result.push_back(Edge(vertexFrom, vertexTo));
		}
	}
	return result;
}

inline vector<Edge> createCyclicGraph(int verticesNumber) {
	vector<Edge> result;
	int curVertex = rand() % (verticesNumber - 1);
	int nextVertex = curVertex + 1;
	result.push_back(Edge(curVertex, nextVertex));
	vector<bool> visited(verticesNumber, false);
	visited[curVertex] = true;
	while (!visited[nextVertex]) {
		visited[nextVertex] = true;
		curVertex = nextVertex;
		nextVertex = rand() % verticesNumber;
		result.push_back(Edge(curVertex, nextVertex));
	}
	return result;
}

inline vector<Edge> createEmptyGraph(int verticesNumber) {
	vector<Edge> result;
	return result;
}

inline vector<Edge> createRareGraph(int verticesNumber) {
	vector<Edge> edgesList;
	int edgesNumber = verticesNumber;
	for (int i = 0; i < edgesNumber; ++i) {
		int vertexFrom = rand() % verticesNumber;
		int vertexTo = rand() % verticesNumber;
		edgesList.push_back(Edge(vertexFrom, vertexTo));
	}
	return edgesList;
}

inline void testMakeCompactGraphMatrix(const vector<Edge>& edgesList, int verticesNumber) {
	auto graph = makeCompactGraph(edgesList, verticesNumber);
	if (NULL == dynamic_cast<MatrixGraph*>(graph.get()))
		throw logic_error("IGraph::makeCompactGraph: FAIL");
}

inline void testMakeCompactGraphList(const vector<Edge>& edgesList, int verticesNumber) {
	auto graph = makeCompactGraph(edgesList, verticesNumber);
	if (NULL == dynamic_cast<IncidenceListGraph*>(graph.get()))
		throw logic_error("IGraph::makeCompactGraph: FAIL");
}

inline void testGetNumberOfVertices(const IGraph& graph, int verticesNumber) {
	if (graph.getNumberOfVertices() != verticesNumber) {
		throw logic_error("IGraph::GetNumberOfVertices: FAIL");
	}
}

inline void testMatrixGetNumberOfVertices(vector<Edge> &edgesList, 	int verticesNumber) {
	try {
		testGetNumberOfVertices(MatrixGraph(edgesList, verticesNumber), verticesNumber);
	}
	catch (const exception& ex) {
		throw logic_error("MatrixGetNumberOfVertices: " + string(ex.what()));
	}
}

inline void testListGetNumberOfVertices(vector<Edge> &edgesList, int verticesNumber) {
	try {
		testGetNumberOfVertices(MatrixGraph(edgesList, verticesNumber), verticesNumber);
	}
	catch (const exception& ex) {
		throw logic_error("MatrixGetNumberOfVertices: " + string(ex.what()));
	}
}

inline void testGetIncidenceList(const IGraph& graph, const vector<Edge> &edgesList, int vertex) {
	set<int> correctIncidenceSet;
	vector<int> incidenceList = graph.getIncidenceList(vertex);
	set<int> incidenceSet(incidenceList.begin(), incidenceList.end());

	for (int edge_index = 0; edge_index < (int)edgesList.size(); ++edge_index) {
		if (edgesList[edge_index].from_ == vertex) {
			correctIncidenceSet.insert(edgesList[edge_index].to_);
		}
	}

	if (incidenceSet != correctIncidenceSet) {
		throw logic_error("IGraph::GetIncidenceList : FAIL");
	}
}

inline void testMatrixGetIncidenceList(const vector<Edge> &edgesList, int verticesNumber) {
	try {
		for (int vertex = 0; vertex < verticesNumber; ++vertex)
			testGetIncidenceList(MatrixGraph(edgesList, verticesNumber), edgesList, vertex);
	}
	catch (const exception& ex) {
		throw logic_error("MatrixGetIncidenceList: " + string(ex.what()));
	}
}

inline void testListGetIncidenceList(const vector<Edge> &edgesList, int verticesNumber) {
	try {
		for (int vertex = 0; vertex < verticesNumber; ++vertex)
			testGetIncidenceList(IncidenceListGraph(edgesList, verticesNumber), edgesList, vertex);
	}
	catch (const exception& ex) {
		throw logic_error("ListGetIncidenceList: " + string(ex.what()));
	}
}

void testOnRandomGraphs() {
	clock_t matrixGraphWorkTime = 0;
	clock_t listGraphWorkTime = 0;
	clock_t timeStart;
	clock_t timeFinish;
	for (int testNo = 0; testNo < MAX_TEST_NO; ++testNo) {
		int verticesNumber = rand() % MAX_VERTICES_NUMBER + 2;
		vector<Edge> edgesList = createRandomGraph(verticesNumber);
		
		timeStart = clock();
		testMatrixGetNumberOfVertices(edgesList, verticesNumber);
		testMatrixGetIncidenceList(edgesList, verticesNumber);
		timeFinish = clock();
		matrixGraphWorkTime += timeFinish - timeStart;
		
		timeStart = clock();
		testListGetNumberOfVertices(edgesList, verticesNumber);
		testListGetIncidenceList(edgesList, verticesNumber);
		timeFinish = clock();
		listGraphWorkTime += timeFinish - timeStart;
	}
	cout << "Test on random graphs: OK" << "\n";
	cout << "Matrix graph time: " << matrixGraphWorkTime << "\n";
	cout << "List graph time: " << listGraphWorkTime << "\n";
	cout << "\n";
}

void testOnFullGraphs() {
	clock_t matrixGraphWorkTime = 0;
	clock_t listGraphWorkTime = 0;
	clock_t timeStart;
	clock_t timeFinish;
	for (int testNo = 0; testNo < MAX_TEST_NO; ++testNo) {
		int verticesNumber = rand() % MAX_VERTICES_NUMBER + 2;
		vector<Edge> edgesList = createFullGraph(verticesNumber);

		timeStart = clock();
		testMatrixGetNumberOfVertices(edgesList, verticesNumber);
		testMatrixGetIncidenceList(edgesList, verticesNumber);
		timeFinish = clock();
		matrixGraphWorkTime += timeFinish - timeStart;

		timeStart = clock();
		testListGetNumberOfVertices(edgesList, verticesNumber);
		testListGetIncidenceList(edgesList, verticesNumber);
		timeFinish = clock();
		listGraphWorkTime += timeFinish - timeStart;

		if (verticesNumber > 10) {
			try {
				testMakeCompactGraphMatrix(edgesList, verticesNumber);
			}
			catch (const exception& ex) {
				throw logic_error("makeCompactGraph: " + string(ex.what()));
			}
		}
	}
	cout << "Test on full graphs: OK" << "\n";
	cout << "Matrix graph time: " << matrixGraphWorkTime << "\n";
	cout << "List graph time: " << listGraphWorkTime << "\n";
	cout << "\n";
}

void testOnEmptyGraphs() {
	clock_t matrixGraphWorkTime = 0;
	clock_t listGraphWorkTime = 0;
	clock_t timeStart;
	clock_t timeFinish;
	for (int testNo = 0; testNo < MAX_TEST_NO; ++testNo) {
		int verticesNumber = rand() % MAX_VERTICES_NUMBER + 2;
		vector<Edge> edgesList = createEmptyGraph(verticesNumber);

		timeStart = clock();
		testMatrixGetNumberOfVertices(edgesList, verticesNumber);
		testMatrixGetIncidenceList(edgesList, verticesNumber);
		timeFinish = clock();
		matrixGraphWorkTime += timeFinish - timeStart;

		timeStart = clock();
		testListGetNumberOfVertices(edgesList, verticesNumber);
		testListGetIncidenceList(edgesList, verticesNumber);
		timeFinish = clock();
		listGraphWorkTime += timeFinish - timeStart;
		
		if (verticesNumber > 10) {
			try {
				testMakeCompactGraphList(edgesList, verticesNumber);
			}
			catch (const exception& ex) {
				throw logic_error("makeCompactGraph: " + string(ex.what()));
			}
		}
	}
	cout << "Test on empty graphs: OK" << "\n";
	cout << "Matrix graph time: " << matrixGraphWorkTime << "\n";
	cout << "List graph time: " << listGraphWorkTime << "\n";
	cout << "\n";
}

void testOnRareGraphs() {
	clock_t matrixGraphWorkTime = 0;
	clock_t listGraphWorkTime = 0;
	clock_t timeStart;
	clock_t timeFinish;
	for (int testNo = 0; testNo < MAX_TEST_NO; ++testNo) {
		int verticesNumber = rand() % MAX_VERTICES_NUMBER + 2;
		vector<Edge> edgesList = createEmptyGraph(verticesNumber);

		timeStart = clock();
		testMatrixGetNumberOfVertices(edgesList, verticesNumber);
		testMatrixGetIncidenceList(edgesList, verticesNumber);
		timeFinish = clock();
		matrixGraphWorkTime += timeFinish - timeStart;

		timeStart = clock();
		testListGetNumberOfVertices(edgesList, verticesNumber);
		testListGetIncidenceList(edgesList, verticesNumber);
		timeFinish = clock();
		listGraphWorkTime += timeFinish - timeStart;

		if (verticesNumber > 10) {
			try {
				testMakeCompactGraphList(edgesList, verticesNumber);
			}
			catch (const exception& ex) {
				throw logic_error("makeCompactGraph: " + string(ex.what()));
			}
		}
	}
	cout << "Test on rare graphs: OK" << "\n";
	cout << "Matrix graph time: " << matrixGraphWorkTime << "\n";
	cout << "List graph time: " << listGraphWorkTime << "\n";
	cout << "\n";
}

inline void testIGraph() {
	testOnRandomGraphs();
	testOnFullGraphs();
	testOnEmptyGraphs();
	testOnRareGraphs();
}